package primary.code08;

import lombok.extern.slf4j.Slf4j;

/**
 * manacher算法，求解连续回文子串的最大长度
 * <p>
 * 分析
 * <p>
 * 一、为了能正确地识别偶数/奇数长度的子串，将对原字符串进行加工，插入任意字符
 * 二、记录当前识别的子串最右边界+1索引r，以及对应的中心索引c
 * 三、分4种情况，加速计算回文半径数组（重点）
 * 1. i>=r, 无法使用先前的回文识别结果，只能暴力处理，初始半径长度仅为自身1
 * 2. i<r, 镜像i'的回文在L内，直接确定半径长度为pArr[i']，也可认为初始长度为 pArr[i']
 * 3. i<r, 镜像i'的回文在L外，直接确定半径长度为r-i，也可认为初始长度为 r-i
 * 4. i<r, 镜像i'的回文在L上，初始长度为 r-i
 */
@Slf4j
public class Code05_Manacher {

    public static int manacher(String rawStr) {
        if (rawStr == null || rawStr.length() <= 1) {
            return 0;
        }
        char[] manacherStr = processRawStr(rawStr);
        int r = -1;
        int c = -1;
        int[] pArr = new int[manacherStr.length];
        int maxRadiusLen = Integer.MIN_VALUE;
        for (int i = 0; i < manacherStr.length; i++) {
            int radiusLen = i < r ? Math.min(r - i, pArr[2 * c - i]) : 1; // 初始长度
            while (i + radiusLen < manacherStr.length && i - radiusLen >= 0) {
                if (manacherStr[i + radiusLen] == manacherStr[i - radiusLen]) {
                    radiusLen++;
                } else {
                    pArr[i] = radiusLen;
                    break; // 遇到不同的字符串，提前结束
                }
            }
            maxRadiusLen = Math.max(maxRadiusLen, radiusLen);
            if (i + pArr[i] > r) {
                r = i + pArr[i];
                c = i;
            }
        }
        return maxRadiusLen - 1; // 回文串的长度 = 加工后回文串半径 - 1
    }

    /**
     * 对原字符串进行加工
     *
     * @param rawStr
     * @return
     */
    private static char[] processRawStr(String rawStr) {
        if (rawStr == null || rawStr.length() == 0) {
            return new char[0];
        }
        char[] charArray = rawStr.toCharArray();
        char[] res = new char[charArray.length * 2 + 1];
        int index = 0;
        for (int i = 0; i < res.length; i++) {
            if (i % 2 == 0) {
                res[i] = '#';
            } else {
                res[i] = charArray[index++];
            }
        }
        return res;
    }

    public static void main(String[] args) {
        //abcba
        String str1 = "afghkjbabcbafherjnjf";
        //abccba
        String str2 = "afghkjbabccbafherjnjf";
        int manacher1 = manacher(str1);
        log.info("str1: {}, max plalindrome length: {}", str1, manacher1);
        int manacher2 = manacher(str2);
        log.info("str2: {}, max plalindrome length: {}", str2, manacher2);
    }
}
